// Created by WXX on 2021/9/3 8:59
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        int n = arr.size();
        quick_sort(arr, 0, n - 1, k - 1);
        vector<int> res;
        for (int i = 0; i < k; i++) res.push_back(arr[i]);
        return res;
    }

    void quick_sort(vector<int> &q, int l, int r, int k) {
        if (l >= r) return;

        int x = q[l + r >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            while (q[++i] < x) ;
            while (q[--j] > x) ;
            if (i < j) swap(q[i], q[j]);
        }

        if (k <= j) quick_sort(q, l, j, k);
        else quick_sort(q, j + 1, r, k);
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> arr = {1, 3, 2};
    OutputBasicArray1D(Solution().smallestK(arr, 2));

    return 0;
}
